package com.squirrel.michale.search1;

import java.util.Arrays;
/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/18 12:15 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class BinarySearch {


    public static int binarySearch(int[] array ,int left,int right,int target) {

        int middle = (left+right)/2;

        if (array[right] < target) {
            return  -1;
        }

        if (target == array[middle]) {
            return middle;
        } else if (array[middle] > target) {
            return binarySearch(array, left, middle, target);
        } else  {
            return binarySearch(array, middle, right, target);
        }
    }

    public static boolean binarySearchWithIterator(int[] sortedArr, int num) {
        if (sortedArr == null || sortedArr.length == 0) {
            return false;
        }
        int L = 0;
        int R = sortedArr.length - 1;
        int mid = 0;
        // L..R
        while (L < R) { // L..R 至少两个数的时候
            mid = L + ((R - L) >> 1);
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return sortedArr[L] == num;
    }

    public static int binarySearchWithRecursive(int[] sortedArray ,int left,int right,int target) {

        if (sortedArray[right] < target) {
            return  -1;
        }

        int middle = left + ((right - left) >> 1);

        if (target == sortedArray[middle]) {
            return middle;
        } else if (sortedArray[middle] > target) {
            return binarySearchWithRecursive(sortedArray, left, middle-1, target);
        } else  {
            return binarySearchWithRecursive(sortedArray, middle+1, right, target);
        }

    }
    public static void main(String[] args) {
        int[] score = new int[]{0,12, 45,56,61,77,80,89, 99, 156, 177, 245, 280, 361, 400};

        int index = binarySearch(score, 0, score.length-1, 500);
        int index2 = binarySearchWithRecursive(score, 0, score.length-1, 0);

        System.out.println(index2);

        Arrays.binarySearch(score, 0, score.length - 1, 0);
    }

}
